fork download
copy 
  1. """
  2.  
  3. Bethany Low
  4. blow100
  5. 969296361
  6.  
  7. 08/06/2020
  8.  
  9. COMPSCI 220 - Assignment 4
  10. Question 2: Tree arcs and cross arcs in DFS
  11.  
  12. Programme
  13.  
  14. 4
  15. 1 3
  16. 2 3
  17. 0
  18.  
  19. 3
  20. 1 2
  21.  
  22. 1
  23. 0
  24.  
  25. """
  26.  
  27. #Import sys and deque library
  28. import sys
  29. from queue import deque
  30.  
  31.  
  32. def dfs(adj):
  33.     ''' Function that does a depth first search on an adjacency list
  34.         of a disgraph, returning the rank of each node in a list. '''
  35.  
  36.     # Setting up queue, and visited, predecessor and rank arrays.
  37.     stack = deque()
  38.     n = len(adj)
  39.     colour = ['White']*n
  40.     pred = ['Null']*n
  41.     seen = [-1]*n
  42.     done = [-1]*n
  43.  
  44.     time = 0
  45.  
  46.     for i in range(0,n-1):
  47.         if colour[i] == 'White':
  48.             dfsvisit(stack, adj, colour, pred, seen, done, time, i)
  49.     return seen, done, pred
  50.  
  51. def dfsvisit(stack, adj, colour, pred, seen, done, time, node):
  52.     colour[node] = 'Grey'
  53.     seen[node] = time
  54.     time = time + 1
  55.     stack.append(node)
  56.  
  57.     while len(stack) != 0:
  58.         u = stack[-1]
  59.  
  60.         l = [i for i in adj[u] if colour[i]=='White']
  61.         if len(l)!=0:
  62.             for i in l:
  63.                 colour[i]='Grey'
  64.                 pred[i] = u
  65.                 seen[i]=time
  66.                 time = time+1
  67.                 stack.append(i)
  68.         else:
  69.             stack.pop()
  70.             colour[node] = 'Black'
  71.             done[node] = time
  72.             time = time + 1
  73.  
  74. """
  75. def recursiveDFSvisit(stack, adj, colour, pred, seen, done, time, node):
  76.     colour[node] = 'Grey'
  77.     seen[node] = time
  78.     time = time + 1
  79.  
  80.     for adj_node in adj[node]:
  81.         if colour[adj_node] == 'White':
  82.             pred[adj_node] = node
  83.             recursiveDFSvisit(stack, adj, colour, pred, seen, done, time, adj_node)
  84.  
  85.     colour[node] = 'Black'
  86.     done[node] = time
  87.     time = time + 1
  88. """    
  89. """
  90. ##########
  91.  
  92. def dfs(adj, node):
  93.  
  94.     # Setting up queue, and visited, predecessor and rank arrays.
  95.     stack = deque()
  96.     n = len(adj)
  97.     visited = [False] * len(adj)
  98.     pred_array = [None] * len(adj)
  99.     seen = []
  100.     done = [None] * len(adj)
  101.     time = 0
  102.  
  103.     # Adding Node 0 to the queue and setting visited and rank values.
  104.     stack.append(node)
  105.     visited[node] = True
  106.     seen.append(node)
  107.     time+=1
  108.  
  109.     # While queue is not empty;
  110.     while len(stack) > 0:
  111.  
  112.         u = stack[-1] # Peek at last item - node u.
  113.         if visited[u] != True:
  114.             seen.append(u[0])
  115.             visited[w] = True
  116.         remove_from_stack = True
  117.         for adj_node in adj[u]:
  118.             if visited[adj_node] != True:
  119.                 visited[adj_node] = True
  120.                 remove_from_stack = False
  121.                 break
  122.         if remove_from_stack:
  123.             stack.pop()
  124.     return seen
  125. """
  126.  
  127. def count_arcs(adj_list, result):
  128.  
  129.     tree_count = 0
  130.     cross_count = 0
  131.  
  132.     #seen = [i for j in seen for i in j]
  133.  
  134.     seen = result[0]
  135.     done = result[1]
  136.     pred = result[2]
  137.  
  138.     for index in range(0, len(adj_list)-1):
  139.         if adj_list[index] != []:
  140.             print(index)
  141.             for j in adj_list[index]:
  142.                 print(j)
  143.                 if seen[index]<seen[j]<done[index]<done[j]:
  144.                     tree_count +=1
  145.                     print("Yes")
  146.                 elif seen[j]<done[j]<seen[index]<done[index]:
  147.                     cross_count +=1
  148.                     print("yes")
  149.  
  150.  
  151.     return(str(tree_count) +","+ str(cross_count))
  152.  
  153.  
  154. #Main Programme - While Loop;
  155. while True:
  156.  
  157.     # Get the order of the digraph.
  158.     order = int(sys.stdin.readline())
  159.  
  160.     # If system reads in zero, then stop programme.
  161.     if order == 0:
  162.         break
  163.  
  164.     # Read in each adjacency list
  165.     adj_list = [[] for i in range(order)]
  166.     for empty_row in adj_list:
  167.         empty_row.extend(int(i) for i in sys.stdin.readline().split())
  168.  
  169.     # Run DFS
  170.     result = dfs(adj_list)
  171.     #result = [dfs(adj_list, n) for n in range(order)]
  172.     print(result)
  173.     arcs = count_arcs(adj_list, result)
  174.  
  175.     # Print 
  176.     print(arcs)
  177.  
  178.  
Success #stdin #stdout 0.04s 10060KB
comments (?)
stdin
copy 
4
1 3
2 3
0

3
1 2

1
0
stdout
copy 
([0, 1, 4, 2], [7, -1, -1, -1], ['Null', 0, 1, 0])
0
1
3
1
2
3
2
0
0,0
([0, 1, 2], [5, -1, -1], ['Null', 0, 0])
0
1
2
0,0
https://ideone.com/d1RDzw
language:
Python 3 (python  3.9.5)
created:
128 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!